package exercise.day12;

import java.util.Arrays;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 筛数法求小于N的所有素数
 * @date 2022/11/18 23:36
 */
public class CountPrimes {
    public int countPrimes(int n){
        boolean[] isPrime = new boolean[n]; // 开辟了一个数组，空间换时间
        Arrays.fill(isPrime,true);
        for (int i = 2;i*i < n;i++){   // 乘法因子的对称性，遍历到根号n就行
            if(isPrime[i]){
                for (int j = i*i;j<n;j +=i){  // 防止计算冗余，也可以优化一下从i的平方开始遍历而不是2*i开始
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for (int i=0;i<n;i++){
            if (isPrime[i]) count++;
        }
        return count;
    }
}
